﻿#define _CRT_SECURE_NO_WARNINGS

//1004. 最大连续1的个数 III
//问题转化成：求数组中⼀段最⻓的连续区间，要求这段区间内0的个数不超过k个

class Solution {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int n = nums.size(), ret = 0;
        int count = 0;//记录窗口中0翻转成1的数量
        for (int right = 0, left = 0; right < n; right++)
        {
            if (nums[right] == 0)
            {
                count++;
            }
            //如果连续区间正好有k个0的话，所以不能count==k作为判断标准
            while (count > k)//有k+1个0
            {
                if (nums[left++] == 0)//出窗口
                    count = k;//上限的话就移一个0出窗口
            }
            ret = max(ret, right - left + 1);

        }
        return ret;
    }
};

//1658. 将 x 减到 0 的最小操作数
//可以直接转换成：找到数组最大连续区间里和为sum-x的

class Solution {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int n = nums.size(), sum = 0;
        int nret = -1;//初始返回值不能设为0，当sum正好=x的情况
        for (int a : nums)
            sum += a;
        sum -= x;
        if (sum < 0)
            return -1;
        int tmp = 0;//统计子数组的和   
        for (int left = 0, right = 0; right < n; right++)
        {
            tmp += nums[right];
            while (tmp > sum)//如果sum小于0的话就是一个死循环的bug
            {
                tmp -= nums[left++];//只有大于sum才出窗口,等于(sum==0)的话还不行,会导致left越界访问
            }
            if (tmp == sum)
                nret = max(nret, right - left + 1);//更新结果

        }
        return nret == -1 ? -1 : n - nret;
    }
};